/*
 * @Author: Starfish_DL
 * @Date: 2020-09-29 11:54:17
 * @LastEditors: Starfish_DL
 * @LastEditTime: 2020-09-29 23:43:41
 * @CurrentVersion: 1.0
 * @Description: 
 */

#include<iostream>
using namespace std;

class iTuple
{
public:
    int x;
    int y;
    iTuple();
    iTuple(int a,int b);
    ~iTuple();
};

iTuple::iTuple()
{
    x=0;
    y=0;
}

iTuple::iTuple(int a,int b)
{
    x=a;
    y=b;
}

iTuple::~iTuple()
{
}

class iTupleLinkStackNode
{
public:
    iTuple tuple;
    iTupleLinkStackNode *next;
    iTupleLinkStackNode();
    iTupleLinkStackNode(int a,int b);
    iTupleLinkStackNode(int a,int b,iTupleLinkStackNode *n);
    ~iTupleLinkStackNode();
};

iTupleLinkStackNode::iTupleLinkStackNode()
{
    tuple=iTuple();
    next=nullptr;
}

iTupleLinkStackNode::iTupleLinkStackNode(int a,int b)
{
    tuple=iTuple(a,b);
    next=nullptr;
}

iTupleLinkStackNode::iTupleLinkStackNode(int a,int b,iTupleLinkStackNode *n)
{
    tuple=iTuple(a,b);
    next=n;
}

iTupleLinkStackNode::~iTupleLinkStackNode()
{
}

class iTupleLinkStack
{
public:
    iTupleLinkStackNode *head;
    iTupleLinkStack();
    void Push(iTuple tuple);
    iTuple getTop();
    bool isEmpty();
    iTuple Pop();
    ~iTupleLinkStack();
};

iTupleLinkStack::iTupleLinkStack()
{
    head=new iTupleLinkStackNode();
}

iTupleLinkStack::~iTupleLinkStack()
{
    iTupleLinkStackNode *p=head,*pre=head->next;
    while (pre!=nullptr)
    {
        delete p;
        p=pre;
        pre=pre->next;
    }
    delete p;
}

void iTupleLinkStack::Push(iTuple tuple)
{
    iTupleLinkStackNode *n=new iTupleLinkStackNode(tuple.x,tuple.y,head->next);
    head->next=n;
}

iTuple iTupleLinkStack::Pop()
{
    if (head->next==nullptr)
    {
        iTuple i=iTuple(0,0);
        return i;
    }
    iTupleLinkStackNode *p=head->next;
    head->next=p->next;
    iTuple temp=p->tuple;
    delete p;
    return temp;
}

bool iTupleLinkStack::isEmpty()
{
    return (head->next==nullptr);
}

iTuple iTupleLinkStack::getTop()
{
    if (head->next==nullptr)
    {
        iTuple i=iTuple(0,0);
        return i;
    }
    return (head->next->tuple);
}

int map[10][10]=
{
    {1,1,1,1,1,1,1,1,1,1}, //0
    {1,0,0,1,0,1,0,1,0,1}, //1
    {1,0,0,1,0,1,0,1,0,1}, //2
    {1,0,0,0,0,1,1,0,0,1}, //3
    {1,0,1,1,1,0,0,0,0,1}, //4
    {1,0,0,0,1,0,0,0,0,1}, //5
    {1,0,1,0,0,0,1,0,0,1}, //6
    {1,0,1,1,1,0,1,1,0,1}, //7
    {1,1,0,0,0,0,0,0,0,1}, //8
    {1,1,1,1,1,1,1,1,1,1}  //9
    //tag 地图的'1'表示墙,'0'表示地面,为了方便将四周设置为墙;
};

bool mgPath(iTuple begin,iTuple end)
{
    //done 自动求解走地图迷宫的算法已完成！
    iTuple myPosition=iTuple(begin.x,begin.y);
    iTupleLinkStack *route=new iTupleLinkStack();
    route->Push(myPosition);
    int direction;
    bool find;
    while (route->isEmpty()==false)
    {
        direction=-1;
        find=false;
        if (myPosition.x==end.x && myPosition.y==end.y)
        {
            while (route->isEmpty()==false)
            {
                cout<<"("<<route->getTop().x<<","<<route->getTop().y<<")"<<endl;
                route->Pop();
            }
            delete route;
            cout<<"The function has been executed successfully!";
            return true;
        }
        while (direction<4 && !find)
        {
            direction++;
            switch (direction)
            {
            case 0:
                if (map[myPosition.x][myPosition.y-1]==0)
                {find=true;}
                break;
            case 1:
                if (map[myPosition.x-1][myPosition.y]==0)
                {find=true;}
                break;
            case 2:
                if (map[myPosition.x][myPosition.y+1]==0)
                {find=true;}
                break;
            case 3:
                if (map[myPosition.x+1][myPosition.y]==0)
                {find=true;}
                break;                    
            default:
                break;
            }
        }
        if (find)
        {
            map[myPosition.x][myPosition.y]=1;
            switch (direction)
            {
            case 0:
                myPosition.y--;
                break;
            case 1:
                myPosition.x--;
                break;
            case 2:
                myPosition.y++;
                break;
            case 3:
                myPosition.x++;
                break;                    
            default:
                break;
            }
            route->Push(myPosition);
        }
        else
        {
            map[myPosition.x][myPosition.y]=1;            
            route->Pop();
            myPosition.x=route->getTop().x;
            myPosition.y=route->getTop().y;
            map[myPosition.x][myPosition.y]=0;            
        }
    }
    delete route;
    cout<<"There is no solution to get out of the map.";
    return false;
}

int main()
{
    iTuple begin=iTuple(1,1);
    iTuple end=iTuple(8,2);
    mgPath(begin,end);
    return 0;
}